import java.util.Arrays;
import java.util.TreeMap;

/**
* @description: 954. 二倍数对数组
* @author hewei
* @date 2022/9/23 15:12
* @version 1.0
*/

public class CanReorderDoubled {

    public static void main(String[] args) {
        int[] nums = {-1, 2};
        System.out.println(new CanReorderDoubled().canReorderDoubled(nums));
    }

    public boolean canReorderDoubled1(int[] arr) {
        Integer[] nums = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nums[i] = arr[i];
        }
        Arrays.sort(nums, (a, b) -> {
            if (a < 0 && b < 0) {
                return Integer.compare(b, a);
            }
            return Integer.compare(a, b);
        });
        int l = 0;
        int r = 1;
        int used = Integer.MAX_VALUE;
        while (r < nums.length) {
            while (r < nums.length && nums[l] == used) {
                ++l;
                if (l == r) ++r;
            }
            while (r < nums.length && Math.abs(nums[r] / 2) < Math.abs(nums[l])) ++r;
            if (r == arr.length || nums[r] % 2 == 1 || nums[r] % 2 == -1 || nums[r] / 2 != nums[l]) return false;
            nums[l] = used;
            nums[r] = used;
            ++l;
            ++r;
        }
        while (l < nums.length) {
            if (nums[l++] != used) return false;
        }
        return true;
    }

    public boolean canReorderDoubled(int[] arr) {
        TreeMap<Integer, Integer> map = new TreeMap<>((a, b) -> {
            if (a < 0 && b < 0) return Integer.compare(b, a);
            return Integer.compare(a, b);
        });
        for (int i : arr) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) == 0) continue;
            if (!map.containsKey(2 * key) || map.get(2 * key) < map.get(key)) return false;
            map.put(2 * key, map.get(2 * key) - map.get(key));
        }
        return true;
    }
}
